#include <iostream>
#include <vector>
#include <chrono>
#include <ctime>
#include <cstdlib>
using namespace std;
using namespace chrono;

vector<int> BubbleSort(vector<int> data)
{
    long long length = data.size();
    int tmp;
    for (long long i = 0; i < length - 1; i++)
    {
        for (long long j = i; j < length - 1; j++)
        {
            if (data[i] > data[j])
            {
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }
    return data;
}

vector<int> SelectionSort(vector<int> data)
{
    long long length = data.size();
    long long min_sub;
    int tmp;
    for (long long i = 0; i < length - 1; i++)
    {
        min_sub = i;
        for (long long j = i + 1; j < length - 2; j++)
        {
            if (data[j] < data[min_sub])
            {
                min_sub = j;
            }
        }
        tmp = data[i];
        data[i] = data[min_sub];
        data[min_sub] = tmp;
    }
    return data;
}

vector<int> InsertionSort(vector<int> data)
{
    vector<int> sorted;
    long long length = data.size();
    bool inserted;
    for (long long i = 0; i < length; i++)
    {
        inserted = false;
        for (long long j = 0; j < i; j++)
        {
            if (sorted[j] > data[i])
            {
                sorted.insert(sorted.begin() + j, data[i]);
                inserted = true;
                break;
            }
        }
        if (!inserted)
        {
            sorted.push_back(data[i]);
        }
    }
    return sorted;
}

void Merge(vector<int> &data, long long left, long long mid, long long right, vector<int> &temp)
{
    long long i = left;
    long long j = mid + 1;
    long long t = 0;
    while (i <= mid && j <= right)
    {
        if (data[i] <= data[j])
        {
            temp[t++] = data[i++];
        }
        else
        {
            temp[t++] = data[j++];
        }
    }
    while (i <= mid)
    {
        temp[t++] = data[i++];
    }
    while (j <= right)
    {
        temp[t++] = data[j++];
    }
    t = 0;
    while (left <= right)
    {
        data[left++] = temp[t++];
    }
}

void MergingSortDo(vector<int> &data, long long left, long long right, vector<int> &temp)
{
    if (left < right)
    {
        long long mid = (left + right) / 2;
        MergingSortDo(data, left, mid, temp);
        MergingSortDo(data, mid + 1, right, temp);
        Merge(data, left, mid, right, temp);
    }
}

vector<int> MergingSort(vector<int> data)
{
    long long length = data.size();
    vector<int> temp(length);
    MergingSortDo(data, 0, length - 1, temp);
    return data;
}

long long Partition(vector<int> &data, long long low, long long high)
{
    long long pivot = data[low];
    while (low < high)
    {
        while (low < high && data[high] >= pivot)
        {
            high--;
        }
        data[low] = data[high];
        while (low < high && data[low] <= pivot)
        {
            low++;
        }
        data[high] = data[low];
    }
    data[low] = pivot;
    return low;
}

void QuickSortDo(vector<int> &data, long long low, long long high)
{
    if (low < high)
    {
        long long pivot = Partition(data, low, high);
        QuickSortDo(data, low, pivot - 1);
        QuickSortDo(data, pivot + 1, high);
    }
}

vector<int> QuickSort(vector<int> data)
{
    long long length = data.size();
    QuickSortDo(data, 0, length - 1);
    return data;
}

void Check(vector<int> data)
{
    vector<int> sorted;
    auto start = system_clock::now();
    sorted = BubbleSort(data);
    auto end = system_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << "冒泡排序花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;

    start = system_clock::now();
    sorted = SelectionSort(data);
    end = system_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << "选择排序花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;

    start = system_clock::now();
    sorted = InsertionSort(data);
    end = system_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << "插入排序花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;

    start = system_clock::now();
    sorted = MergingSort(data);
    end = system_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << "归并排序花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;

    start = system_clock::now();
    sorted = QuickSort(data);
    end = system_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << "快速排序花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;
}

int main()
{
    srand((unsigned)time(NULL));
    vector<int> data;
    long long size = 100;
    long long i, j, maxdigit;
    std::cout << "请输入最大数字的位数" << endl;
    std::cin >> maxdigit;
    maxdigit -= 2;
    for (j = 0; j < maxdigit; j++)
    {
        cout << "数据量：" << size << endl;
        data.clear();
        for (i = 0; i < size; i++)
        {
            data.push_back(rand());
        }
        Check(data);
        size *= 10;
    }
    getchar();
    getchar();
    getchar();
    getchar();
}